package com.gorkr.backtracking;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author gorkr
 * @date 2022/06/22 09:48
 * 怎么祛重的问题
 * 如何在回溯中去重呢？ i+1
 * 输入有重 输出无重
 **/
public class M40CombinationSumII {


//    private List<List<Integer>> res = new ArrayList<>();
    private Set<List<Integer>> res = new HashSet<>();
    private LinkedList<Integer> track = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if(candidates.length==0){
            return new ArrayList<>(res);
        }
        Arrays.sort(candidates);

        backTracking(candidates,target,0,0,new boolean[candidates.length]);
        return new ArrayList<>(res);
    }

    private void backTracking(int[] candidates,int target, int sum, int start, boolean[] used) {

        if (sum == target) {
            res.add(new LinkedList<>(track));
            return;
        } else if (sum > target) {
            return;
        }


        // 如何将左边的剪掉 这个start 是关键

        for (int i = start; i < candidates.length; i++) {
            // 大减枝
            if(candidates[i] > target){
                break;
            }

            // todo:小减枝


//            if(used[i]){
//                continue;
//            }
            // 做选择
            sum += candidates[i];
            track.add(candidates[i]);
            used[i] = true;
            backTracking(candidates, target, sum, i+1,used);  // 这里 start 传入i 是关键
            // 撤销
            sum -= candidates[i];
            track.removeLast();
            used[i] = false;
        }

    }

    @Test
    public void test(){
        int[] candidates = {10,1,2,7,6,1,5};
        int target = 8;
        System.out.println(combinationSum2(candidates, target));
    }

}
    